package knapsack;

import java.io.*;
import java.util.ArrayList;
import java.util.List;


/**
 * Created by alex on 22/12/2016.
 */
public class KnapsackProblemSolver {
    String filePath = "src/testknapsack/Knapsack.txt";
    int MAXGENERATION = 2000;
    int scale = 500;//种群中个体数量
    int CL;//染色体长度

    int knapsackSize;
    int itemNum;

    //数据
    double[][] items;

    //累计概率
    double[] P;
    double[] fitnesses;

    int[][] population;
    int[][] winners;

    int[] bestGene;
    double bestPrice;
    double bestWeight;

    //交叉概率 和 变异概率
    double Pc = 0.9;
    double Pm = 0.1;

    double alpha;
    double beta;

    List<Double> averages=new ArrayList<>();
    List<Double> bests = new ArrayList<>();


    public KnapsackProblemSolver(int scale, double Pc, double Pm) {
        this.scale = scale;
        this.Pc = Pc;
        this.Pm = Pm;
        if (scale % 2 == 1) {
            this.scale += 1;
        }
        init(this.scale);
    }

    public KnapsackProblemSolver() {
        init(scale);
    }

    private void initPara(){
        int n = MAXGENERATION/3;
        alpha = (this.Pc-0.1)/(double)n;
        beta = (0.5-this.Pm)/(double) n;
    }

    //读入数据
    private void initItems() {
        File file = new File(filePath);
        try {
            BufferedReader br = new BufferedReader(new FileReader(file));
            String line = br.readLine();
            String[] data = line.split(" ");
            knapsackSize = Integer.parseInt(data[0]);
            itemNum = Integer.parseInt(data[1]);
            CL = itemNum;
            bestGene = new int[CL];

            items = new double[itemNum][2];
            int count = 0;
            while ((line = br.readLine()) != null) {
                data = line.split(" ");
                items[count][0] = Double.parseDouble(data[0]);
                items[count][1] = Double.parseDouble(data[1]);
                count++;
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    //初始化种群
    private void initPopulation(int scale, int CL) {
        population = new int[scale][CL];
        winners = new int[scale][CL];

        //初始化旧种群
        for (int i = 0; i < scale; i++) {
            for (int j = 0; j < CL; j++) {
                double r = Math.random();
                if (r < 0.5)
                    population[i][j] = 0;
                else
                    population[i][j] = 1;
            }
        }
    }

    private void init(int scale) {
        P = new double[scale];
        fitnesses = new double[scale];

        initItems();
        initPopulation(scale, CL);
        initPara();
    }


    private double computeFitness(int[] chromosome) {
        double fitness = 0;
        double weight = 0;
        for (int i = 0; i < chromosome.length; i++) {
            if (chromosome[i] == 1) {
                fitness += this.items[i][1];
                weight += this.items[i][0];
            }
        }
        if (weight > knapsackSize+1) {
            //todo: 直接return 0 合适吗？
            return 0;
        } else {
            return fitness;
        }
    }


    private void computeFitness() {
        for (int i = 0; i < population.length; i++) {
            fitnesses[i] = computeFitness(population[i]);
        }
    }


    //计算累积概率
    private void computeP() {
        double sum = 0;
        for (double fitness : fitnesses) {
            sum += fitness;
        }
        sum += fitnesses.length;

        double tmp = 0;
        for (int i = 0; i < P.length; i++) {
            P[i] = tmp + (fitnesses[i] + 1) / sum;
            tmp = P[i];
        }
    }


    public void select() {
        copy(bestGene,winners[0]);

        for (int i = 1; i < scale; i++) {
            double random = Math.random();
            int index = 0;

            for (int j = 0; j < P.length; j++) {
                if (random < P[j]) {
                    index = j;
                    break;
                }
            }
            copy(population[index], winners[i]);
        }
    }


    private void copy(int[] src, int[] dest) {
        for (int i = 0; i < src.length; i++) {
            dest[i] = src[i];
        }
    }


    public void andOrCross() {
        for (int i = 0; i < scale - 1; i += 2) {
            double r = Math.random();
            if (r < Pc) {
                int[] orGene = or(winners[i], winners[i + 1]);
                int[] andGene = and(winners[i], winners[i + 1]);
                copy(orGene, population[i]);
                copy(andGene, population[i + 1]);
            } else {
                copy(winners[i], population[i]);
                copy(winners[i + 1], population[i + 1]);
            }
        }
    }

    public void randomCross(){
        for (int i = 0; i < scale - 1; i += 2) {
            double r = Math.random();
            if (r < Pc) {
                int low = (int)(Math.random()*CL);
                int high = (int)(Math.random()*CL);
                while (low==high){
                    high = (int)(Math.random()*CL);
                }
                if (low>high){
                    int tmp = low;
                    low = high;
                    high = tmp;
                }
                int[] gene1 = new int[itemNum];
                int[] gene2 = new int[itemNum];

                for (int j = 0;j<itemNum;j++){
                    if (j<low || j >= high){
                        gene1[j] = winners[i][j];
                        gene2[j] = winners[i+1][j];
                    }else if (j>= low && j<high){
                        gene1[j] = winners[i+1][j];
                        gene2[j] = winners[i][j];
                    }
                    copy(gene1,population[i]);
                    copy(gene2,population[i+1]);
                }
            } else {
                copy(winners[i], population[i]);
                copy(winners[i + 1], population[i + 1]);
            }
        }
    }


    private double computePrice(int i){
        int[] gen = winners[i];
        double price = 0;
        for (int j = 0;j<gen.length;j++){
            if (gen[j]==1){
                price+= items[j][1];
            }
        }
        return price;
    }


    private int[] and(int[] gene1, int[] gene2) {
        int[] andGene = new int[gene1.length];
        for (int i = 0; i < gene1.length; i++) {
            if (gene1[i] == 0 || gene2[i] == 0) {
                andGene[i] = 0;
            } else {
                andGene[i] = 1;
            }
        }
        return andGene;
    }

    private int[] or(int[] gene1, int[] gene2) {
        int[] orGene = new int[gene1.length];
        for (int i = 0; i < gene1.length; i++) {
            if (gene1[i] == 1 || gene2[i] == 1) {
                orGene[i] = 1;
            } else {
                orGene[i] = 0;
            }
        }
        return orGene;
    }

    public void mutate() {
        for (int i = 0; i < scale; i++) {
            double r = Math.random();
            if (r < Pm) {
                int num = (int) (Math.random() * 10);
                for (int j = 0; j < num; j++) {
                    int index = (int) (Math.random() * itemNum);
                    int d = population[i][index];
                    if (d == 0) {
                        population[i][index] = 1;
                    } else {
                        population[i][index] = 0;
                    }
                }
            }
        }
    }

    private double evaluate() {
        double price = 0;
        double tmpPrice = 0;
        int maxIndex = 0;
        double tmpWeight = 0;
        double average = 0;
        for (int i = 0; i < population.length; i++) {
            for (int j = 0; j < itemNum; j++) {
                if (population[i][j] == 1) {
                    tmpPrice += items[j][1];
                    tmpWeight += items[j][0];
                    average+= items[j][1];
                }
            }
            if (tmpWeight <= knapsackSize+0.000001) {
                if (tmpPrice > price) {
                    price = tmpPrice;
                    maxIndex = i;
                }
                if (price > bestPrice) {
                    bestPrice = price;
                    copy(population[i], bestGene);
                }
                tmpPrice = 0;
                tmpWeight = 0;
            }
        }
        average/=population.length;
        System.out.println("average: "+average+" best :"+bestPrice);
        averages.add(average);
        bests.add(bestPrice);

        double weight = 0;
        for (int i = 0; i < itemNum; i++) {
            if (population[maxIndex][i] == 1) {
                weight += items[i][0];
            }
        }
        return price;
    }


    public void evolve() {
        for (int i = 0; i < MAXGENERATION; i++) {
            System.out.print("generation: "+i);

            computeFitness();

            computeP();

            evaluate();

            select();

//            randomCross();
            andOrCross();

            mutate();
        }

        double weight = 0;
        for (int i = 0; i < bestGene.length; i++) {
            System.out.println((i + 1) + " " + bestGene[i]);
            if (bestGene[i] == 1) {
                weight += items[i][0];
            }
        }
        print(bestGene);
        System.out.println("Price " + bestPrice);
        System.out.println("Weight " + weight);
        writeFile();
        try {
            writeData();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void writeFile(){
        String outfile= "src/testknapsack/Knapsack-";
        int dot = filePath.indexOf(".");
        outfile+=filePath.charAt(dot-1)+"[14302010041].txt";
        try {
            FileWriter fw = new FileWriter(outfile);
            fw.write(bestPrice+"\n");
            double price = 0;
            for (int i = 0; i < bestGene.length; i++) {
                System.out.println((i + 1) + " " + bestGene[i]);
                if (bestGene[i] == 1) {
                    price += items[i][1];
                }
                fw.write((i+1)+" "+bestGene[i]+"\n");
            }
            fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void writeData() throws IOException {
        String avefile = "src/testknapsack/ave1.txt";
        FileWriter fw = new FileWriter(avefile);

        for (double ave:averages){
            fw.write(ave+"\n");
        }
        fw.close();

        String bestfile = "src/testknapsack/best1.txt";
        FileWriter fw2 = new FileWriter(bestfile);

        for (double best:bests){
            fw2.write(best+"\n");
        }
        fw2.close();

    }

    private void print(double[] array) {
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i]);
        System.out.println();
    }

    private void print(int[] array) {
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i]);
        System.out.println();
    }

    public static void main(String[] args) {
        KnapsackProblemSolver solver = new KnapsackProblemSolver();
        solver.evolve();
    }

}
